package info.xiao.dataStructrue.array;

import java.util.HashMap;
import java.util.Map;

/**
 * @Classname FindShortestSubArray
 * @Description 数组的度
 * @Url :https://leetcode.cn/problems/degree-of-an-array/
 * @Date 2023/3/27 9:39
 * @Created by 晓龙Oba
 */
public class FindShortestSubArray {
    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 1};
        int result = findShortestSubArray(nums);
    }

    private static int findShortestSubArray(int[] nums) {
        // 第一步 记录每一个元素第一次出现的位置
        Map<Integer, Integer> startIndex = new HashMap<>();
        Map<Integer, Integer> length = new HashMap<>();
        // 第二步 记录每一个元素出现的次数
        Map<Integer, Integer> timesMap = new HashMap<>();
        // 设置最大值标记
        Integer maxValue = -1;
        for (int i = 0; i < nums.length; i++) {
            startIndex.put(nums[i], startIndex.get(nums[i]) == null ? i : startIndex.get(nums[i]));
            length.put(nums[i], i - startIndex.get(nums[i]) + 1);
            timesMap.put(nums[i], timesMap.get(nums[i]) == null ? 1 : timesMap.get(nums[i]) + 1);
            if (i == 0) {
                maxValue = nums[i];
                continue;
            }
            Integer times = timesMap.get(maxValue);
            Integer minLenth = length.get(maxValue);
            if (timesMap.get(nums[i]) > times) {
                maxValue = nums[i];
            } else if (timesMap.get(nums[i]) == times) {
                maxValue = length.get(nums[i]) < minLenth ? nums[i] : maxValue;
            }
        }

        return length.get(maxValue);
    }

}
